<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-pragma">{-# LANGUAGE NondecreasingIndentation #-}</span><span>
</span><span id="line-2"></span><span class="hs-comment">-- | A simple mutable union-find data structure.</span><span>
</span><span id="line-3"></span><span class="hs-comment">--</span><span>
</span><span id="line-4"></span><span class="hs-comment">-- It is used in a unification algorithm for backpack mix-in linking.</span><span>
</span><span id="line-5"></span><span class="hs-comment">--</span><span>
</span><span id="line-6"></span><span class="hs-comment">-- This implementation is based off of the one in \&quot;The Essence of ML Type</span><span>
</span><span id="line-7"></span><span class="hs-comment">-- Inference\&quot;. (N.B. the union-find package is also based off of this.)</span><span>
</span><span id="line-8"></span><span class="hs-comment">--</span><span>
</span><span id="line-9"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Distribution.Utils.UnionFind</span><span> </span><span class="hs-special">(</span><span>
</span><span id="line-10"></span><span>    </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier">Point</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-11"></span><span>    </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#fresh"><span class="hs-identifier">fresh</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-12"></span><span>    </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#find"><span class="hs-identifier">find</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-13"></span><span>    </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#union"><span class="hs-identifier">union</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-14"></span><span>    </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#equivalent"><span class="hs-identifier">equivalent</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-15"></span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-16"></span><span>
</span><span id="line-17"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.STRef.html#"><span class="hs-identifier">Data.STRef</span></a></span><span>
</span><span id="line-18"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.html#"><span class="hs-identifier">Control.Monad</span></a></span><span>
</span><span id="line-19"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.ST.html#"><span class="hs-identifier">Control.Monad.ST</span></a></span><span>
</span><span id="line-20"></span><span>
</span><span id="line-21"></span><span class="hs-comment">-- | A variable which can be unified; alternately, this can be thought</span><span>
</span><span id="line-22"></span><span class="hs-comment">-- of as an equivalence class with a distinguished representative.</span><span>
</span><span id="line-23"></span><span class="hs-keyword">newtype</span><span> </span><span id="Point"><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-var">Point</span></a></span></span><span> </span><span id="local-6989586621679651418"><span class="annot"><a href="#local-6989586621679651418"><span class="hs-identifier hs-type">s</span></a></span></span><span> </span><span id="local-6989586621679651417"><span class="annot"><a href="#local-6989586621679651417"><span class="hs-identifier hs-type">a</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="Point"><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-var">Point</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.STRef.html#STRef"><span class="hs-identifier hs-type">STRef</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651418"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-type">Link</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651418"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651417"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-24"></span><span>    </span><span class="hs-keyword">deriving</span><span> </span><span class="hs-special">(</span><span id="local-6989586621679651342"><span id="local-6989586621679651347"><span class="annot"><span class="annottext">Point s a -&gt; Point s a -&gt; Bool
(Point s a -&gt; Point s a -&gt; Bool)
-&gt; (Point s a -&gt; Point s a -&gt; Bool) -&gt; Eq (Point s a)
forall a. (a -&gt; a -&gt; Bool) -&gt; (a -&gt; a -&gt; Bool) -&gt; Eq a
forall s a. Point s a -&gt; Point s a -&gt; Bool
/= :: Point s a -&gt; Point s a -&gt; Bool
$c/= :: forall s a. Point s a -&gt; Point s a -&gt; Bool
== :: Point s a -&gt; Point s a -&gt; Bool
$c== :: forall s a. Point s a -&gt; Point s a -&gt; Bool
</span><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var">Eq</span></span></span></span><span class="hs-special">)</span><span>
</span><span id="line-25"></span><span>
</span><span id="line-26"></span><span class="hs-comment">-- | Mutable write to a 'Point'</span><span>
</span><span id="line-27"></span><span id="local-6989586621679651415"><span id="local-6989586621679651416"><span class="annot"><a href="Distribution.Utils.UnionFind.html#writePoint"><span class="hs-identifier hs-type">writePoint</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651416"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651415"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-type">Link</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651416"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651415"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.ST.html#ST"><span class="hs-identifier hs-type">ST</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651416"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-special">)</span></span></span><span>
</span><span id="line-28"></span><span id="writePoint"><span class="annot"><span class="annottext">writePoint :: forall s a. Point s a -&gt; Link s a -&gt; ST s ()
</span><a href="Distribution.Utils.UnionFind.html#writePoint"><span class="hs-identifier hs-var hs-var">writePoint</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span id="local-6989586621679651336"><span class="annot"><span class="annottext">STRef s (Link s a)
</span><a href="#local-6989586621679651336"><span class="hs-identifier hs-var">v</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">STRef s (Link s a) -&gt; Link s a -&gt; ST s ()
forall s a. STRef s a -&gt; a -&gt; ST s ()
</span><a href="../../base/src/GHC.STRef.html#writeSTRef"><span class="hs-identifier hs-var">writeSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s (Link s a)
</span><a href="#local-6989586621679651336"><span class="hs-identifier hs-var">v</span></a></span><span>
</span><span id="line-29"></span><span>
</span><span id="line-30"></span><span class="hs-comment">-- | Read the current value of 'Point'.</span><span>
</span><span id="line-31"></span><span id="local-6989586621679651408"><span id="local-6989586621679651409"><span class="annot"><a href="Distribution.Utils.UnionFind.html#readPoint"><span class="hs-identifier hs-type">readPoint</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651409"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651408"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.ST.html#ST"><span class="hs-identifier hs-type">ST</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651409"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-type">Link</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651409"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651408"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-32"></span><span id="readPoint"><span class="annot"><span class="annottext">readPoint :: forall s a. Point s a -&gt; ST s (Link s a)
</span><a href="Distribution.Utils.UnionFind.html#readPoint"><span class="hs-identifier hs-var hs-var">readPoint</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span id="local-6989586621679651333"><span class="annot"><span class="annottext">STRef s (Link s a)
</span><a href="#local-6989586621679651333"><span class="hs-identifier hs-var">v</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">STRef s (Link s a) -&gt; ST s (Link s a)
forall s a. STRef s a -&gt; ST s a
</span><a href="../../base/src/GHC.STRef.html#readSTRef"><span class="hs-identifier hs-var">readSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s (Link s a)
</span><a href="#local-6989586621679651333"><span class="hs-identifier hs-var">v</span></a></span><span>
</span><span id="line-33"></span><span>
</span><span id="line-34"></span><span class="hs-comment">-- | The internal data structure for a 'Point', which either records</span><span>
</span><span id="line-35"></span><span class="hs-comment">-- the representative element of an equivalence class, or a link to</span><span>
</span><span id="line-36"></span><span class="hs-comment">-- the 'Point' that actually stores the representative type.</span><span>
</span><span id="line-37"></span><span class="hs-keyword">data</span><span> </span><span id="Link"><span class="annot"><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-var">Link</span></a></span></span><span> </span><span id="local-6989586621679651392"><span class="annot"><a href="#local-6989586621679651392"><span class="hs-identifier hs-type">s</span></a></span></span><span> </span><span id="local-6989586621679651391"><span class="annot"><a href="#local-6989586621679651391"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-38"></span><span>    </span><span class="hs-comment">-- NB: it is too bad we can't say STRef Int#; the weights remain boxed</span><span>
</span><span id="line-39"></span><span>    </span><span class="hs-glyph">=</span><span> </span><span id="Info"><span class="annot"><a href="Distribution.Utils.UnionFind.html#Info"><span class="hs-identifier hs-var">Info</span></a></span></span><span> </span><span class="hs-pragma">{-# UNPACK</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="hs-glyph">!</span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.STRef.html#STRef"><span class="hs-identifier hs-type">STRef</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651392"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span class="hs-special">)</span><span> </span><span class="hs-pragma">{-# UNPACK</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="hs-glyph">!</span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.STRef.html#STRef"><span class="hs-identifier hs-type">STRef</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651392"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651391"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-40"></span><span>    </span><span class="hs-glyph">|</span><span> </span><span id="Link"><span class="annot"><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-var">Link</span></a></span></span><span> </span><span class="hs-pragma">{-# UNPACK</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="hs-glyph">!</span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651392"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651391"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-41"></span><span>
</span><span id="line-42"></span><span class="hs-comment">-- | Create a fresh equivalence class with one element.</span><span>
</span><span id="line-43"></span><span id="local-6989586621679651402"><span id="local-6989586621679651403"><span class="annot"><a href="Distribution.Utils.UnionFind.html#fresh"><span class="hs-identifier hs-type">fresh</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="#local-6989586621679651403"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.ST.html#ST"><span class="hs-identifier hs-type">ST</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651402"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651402"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651403"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-44"></span><span id="fresh"><span class="annot"><span class="annottext">fresh :: forall a s. a -&gt; ST s (Point s a)
</span><a href="Distribution.Utils.UnionFind.html#fresh"><span class="hs-identifier hs-var hs-var">fresh</span></a></span></span><span> </span><span id="local-6989586621679651322"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679651322"><span class="hs-identifier hs-var">desc</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-45"></span><span>    </span><span id="local-6989586621679651321"><span class="annot"><span class="annottext">STRef s Int
</span><a href="#local-6989586621679651321"><span class="hs-identifier hs-var">weight</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Int -&gt; ST s (STRef s Int)
forall a s. a -&gt; ST s (STRef s a)
</span><a href="../../base/src/GHC.STRef.html#newSTRef"><span class="hs-identifier hs-var">newSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">1</span></span><span>
</span><span id="line-46"></span><span>    </span><span id="local-6989586621679651319"><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651319"><span class="hs-identifier hs-var">descriptor</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">a -&gt; ST s (STRef s a)
forall a s. a -&gt; ST s (STRef s a)
</span><a href="../../base/src/GHC.STRef.html#newSTRef"><span class="hs-identifier hs-var">newSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679651322"><span class="hs-identifier hs-var">desc</span></a></span><span>
</span><span id="line-47"></span><span>    </span><span class="annot"><span class="annottext">STRef s (Link s a) -&gt; Point s a
forall s a. STRef s (Link s a) -&gt; Point s a
</span><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-var">Point</span></a></span><span> </span><span class="annot"><span class="annottext">(STRef s (Link s a) -&gt; Point s a)
-&gt; ST s (STRef s (Link s a)) -&gt; ST s (Point s a)
forall (f :: * -&gt; *) a b. Functor f =&gt; (a -&gt; b) -&gt; f a -&gt; f b
</span><a href="../../base/src/GHC.Base.html#fmap"><span class="hs-operator hs-var">`fmap`</span></a></span><span> </span><span class="annot"><span class="annottext">Link s a -&gt; ST s (STRef s (Link s a))
forall a s. a -&gt; ST s (STRef s a)
</span><a href="../../base/src/GHC.STRef.html#newSTRef"><span class="hs-identifier hs-var">newSTRef</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">STRef s Int -&gt; STRef s a -&gt; Link s a
forall s a. STRef s Int -&gt; STRef s a -&gt; Link s a
</span><a href="Distribution.Utils.UnionFind.html#Info"><span class="hs-identifier hs-var">Info</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s Int
</span><a href="#local-6989586621679651321"><span class="hs-identifier hs-var">weight</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651319"><span class="hs-identifier hs-var">descriptor</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-48"></span><span>
</span><span id="line-49"></span><span class="hs-comment">-- | Flatten any chains of links, returning a 'Point'</span><span>
</span><span id="line-50"></span><span class="hs-comment">-- which points directly to the canonical representation.</span><span>
</span><span id="line-51"></span><span id="local-6989586621679651389"><span id="local-6989586621679651390"><span class="annot"><a href="Distribution.Utils.UnionFind.html#repr"><span class="hs-identifier hs-type">repr</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651390"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651389"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.ST.html#ST"><span class="hs-identifier hs-type">ST</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651390"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651390"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651389"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-52"></span><span id="repr"><span class="annot"><span class="annottext">repr :: forall s a. Point s a -&gt; ST s (Point s a)
</span><a href="Distribution.Utils.UnionFind.html#repr"><span class="hs-identifier hs-var hs-var">repr</span></a></span></span><span> </span><span id="local-6989586621679651308"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651308"><span class="hs-identifier hs-var">point</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Link s a)
forall s a. Point s a -&gt; ST s (Link s a)
</span><a href="Distribution.Utils.UnionFind.html#readPoint"><span class="hs-identifier hs-var">readPoint</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651308"><span class="hs-identifier hs-var">point</span></a></span><span> </span><span class="annot"><span class="annottext">ST s (Link s a)
-&gt; (Link s a -&gt; ST s (Point s a)) -&gt; ST s (Point s a)
forall (m :: * -&gt; *) a b. Monad m =&gt; m a -&gt; (a -&gt; m b) -&gt; m b
</span><a href="../../base/src/GHC.Base.html#%3E%3E%3D"><span class="hs-operator hs-var">&gt;&gt;=</span></a></span><span> </span><span class="hs-glyph">\</span><span id="local-6989586621679651307"><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651307"><span class="hs-identifier hs-var">r</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span>
</span><span id="line-53"></span><span>  </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651307"><span class="hs-identifier hs-var">r</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-54"></span><span>    </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-type">Link</span></a></span><span> </span><span id="local-6989586621679651306"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651306"><span class="hs-identifier hs-var">point'</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-55"></span><span>        </span><span id="local-6989586621679651305"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651305"><span class="hs-identifier hs-var">point''</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Point s a)
forall s a. Point s a -&gt; ST s (Point s a)
</span><a href="Distribution.Utils.UnionFind.html#repr"><span class="hs-identifier hs-var">repr</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651306"><span class="hs-identifier hs-var">point'</span></a></span><span>
</span><span id="line-56"></span><span>        </span><span class="annot"><span class="annottext">Bool -&gt; ST s () -&gt; ST s ()
forall (f :: * -&gt; *). Applicative f =&gt; Bool -&gt; f () -&gt; f ()
</span><a href="../../base/src/GHC.Base.html#when"><span class="hs-identifier hs-var">when</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651305"><span class="hs-identifier hs-var">point''</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; Point s a -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">/=</span></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651306"><span class="hs-identifier hs-var">point'</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">(ST s () -&gt; ST s ()) -&gt; ST s () -&gt; ST s ()
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-57"></span><span>            </span><span class="annot"><span class="annottext">Point s a -&gt; Link s a -&gt; ST s ()
forall s a. Point s a -&gt; Link s a -&gt; ST s ()
</span><a href="Distribution.Utils.UnionFind.html#writePoint"><span class="hs-identifier hs-var">writePoint</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651308"><span class="hs-identifier hs-var">point</span></a></span><span> </span><span class="annot"><span class="annottext">(Link s a -&gt; ST s ()) -&gt; ST s (Link s a) -&gt; ST s ()
forall (m :: * -&gt; *) a b. Monad m =&gt; (a -&gt; m b) -&gt; m a -&gt; m b
</span><a href="../../base/src/GHC.Base.html#%3D%3C%3C"><span class="hs-operator hs-var">=&lt;&lt;</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Link s a)
forall s a. Point s a -&gt; ST s (Link s a)
</span><a href="Distribution.Utils.UnionFind.html#readPoint"><span class="hs-identifier hs-var">readPoint</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651306"><span class="hs-identifier hs-var">point'</span></a></span><span>
</span><span id="line-58"></span><span>        </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Point s a)
forall (m :: * -&gt; *) a. Monad m =&gt; a -&gt; m a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var">return</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651305"><span class="hs-identifier hs-var">point''</span></a></span><span>
</span><span id="line-59"></span><span>    </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Info"><span class="hs-identifier hs-type">Info</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s Int
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">STRef s a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Point s a)
forall (m :: * -&gt; *) a. Monad m =&gt; a -&gt; m a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var">return</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651308"><span class="hs-identifier hs-var">point</span></a></span><span>
</span><span id="line-60"></span><span>
</span><span id="line-61"></span><span class="hs-comment">-- | Return the canonical element of an equivalence</span><span>
</span><span id="line-62"></span><span class="hs-comment">-- class 'Point'.</span><span>
</span><span id="line-63"></span><span id="local-6989586621679651373"><span id="local-6989586621679651374"><span class="annot"><a href="Distribution.Utils.UnionFind.html#find"><span class="hs-identifier hs-type">find</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651374"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651373"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.ST.html#ST"><span class="hs-identifier hs-type">ST</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651374"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651373"><span class="hs-identifier hs-type">a</span></a></span></span></span><span>
</span><span id="line-64"></span><span id="find"><span class="annot"><span class="annottext">find :: forall s a. Point s a -&gt; ST s a
</span><a href="Distribution.Utils.UnionFind.html#find"><span class="hs-identifier hs-var hs-var">find</span></a></span></span><span> </span><span id="local-6989586621679651298"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651298"><span class="hs-identifier hs-var">point</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-65"></span><span>    </span><span class="hs-comment">-- Optimize length 0 and 1 case at expense of</span><span>
</span><span id="line-66"></span><span>    </span><span class="hs-comment">-- general case</span><span>
</span><span id="line-67"></span><span>    </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Link s a)
forall s a. Point s a -&gt; ST s (Link s a)
</span><a href="Distribution.Utils.UnionFind.html#readPoint"><span class="hs-identifier hs-var">readPoint</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651298"><span class="hs-identifier hs-var">point</span></a></span><span> </span><span class="annot"><span class="annottext">ST s (Link s a) -&gt; (Link s a -&gt; ST s a) -&gt; ST s a
forall (m :: * -&gt; *) a b. Monad m =&gt; m a -&gt; (a -&gt; m b) -&gt; m b
</span><a href="../../base/src/GHC.Base.html#%3E%3E%3D"><span class="hs-operator hs-var">&gt;&gt;=</span></a></span><span> </span><span class="hs-glyph">\</span><span id="local-6989586621679651297"><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651297"><span class="hs-identifier hs-var">r</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span>
</span><span id="line-68"></span><span>      </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651297"><span class="hs-identifier hs-var">r</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-69"></span><span>        </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Info"><span class="hs-identifier hs-type">Info</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s Int
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679651296"><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651296"><span class="hs-identifier hs-var">d_ref</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">STRef s a -&gt; ST s a
forall s a. STRef s a -&gt; ST s a
</span><a href="../../base/src/GHC.STRef.html#readSTRef"><span class="hs-identifier hs-var">readSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651296"><span class="hs-identifier hs-var">d_ref</span></a></span><span>
</span><span id="line-70"></span><span>        </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-type">Link</span></a></span><span> </span><span id="local-6989586621679651295"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651295"><span class="hs-identifier hs-var">point'</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Link s a)
forall s a. Point s a -&gt; ST s (Link s a)
</span><a href="Distribution.Utils.UnionFind.html#readPoint"><span class="hs-identifier hs-var">readPoint</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651295"><span class="hs-identifier hs-var">point'</span></a></span><span> </span><span class="annot"><span class="annottext">ST s (Link s a) -&gt; (Link s a -&gt; ST s a) -&gt; ST s a
forall (m :: * -&gt; *) a b. Monad m =&gt; m a -&gt; (a -&gt; m b) -&gt; m b
</span><a href="../../base/src/GHC.Base.html#%3E%3E%3D"><span class="hs-operator hs-var">&gt;&gt;=</span></a></span><span> </span><span class="hs-glyph">\</span><span id="local-6989586621679651294"><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651294"><span class="hs-identifier hs-var">r'</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span>
</span><span id="line-71"></span><span>          </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651294"><span class="hs-identifier hs-var">r'</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-72"></span><span>            </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Info"><span class="hs-identifier hs-type">Info</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s Int
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679651293"><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651293"><span class="hs-identifier hs-var">d_ref</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">STRef s a -&gt; ST s a
forall s a. STRef s a -&gt; ST s a
</span><a href="../../base/src/GHC.STRef.html#readSTRef"><span class="hs-identifier hs-var">readSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651293"><span class="hs-identifier hs-var">d_ref</span></a></span><span>
</span><span id="line-73"></span><span>            </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-type">Link</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Point s a)
forall s a. Point s a -&gt; ST s (Point s a)
</span><a href="Distribution.Utils.UnionFind.html#repr"><span class="hs-identifier hs-var">repr</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651298"><span class="hs-identifier hs-var">point</span></a></span><span> </span><span class="annot"><span class="annottext">ST s (Point s a) -&gt; (Point s a -&gt; ST s a) -&gt; ST s a
forall (m :: * -&gt; *) a b. Monad m =&gt; m a -&gt; (a -&gt; m b) -&gt; m b
</span><a href="../../base/src/GHC.Base.html#%3E%3E%3D"><span class="hs-operator hs-var">&gt;&gt;=</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s a
forall s a. Point s a -&gt; ST s a
</span><a href="Distribution.Utils.UnionFind.html#find"><span class="hs-identifier hs-var">find</span></a></span><span>
</span><span id="line-74"></span><span>
</span><span id="line-75"></span><span class="hs-comment">-- | Unify two equivalence classes, so that they share</span><span>
</span><span id="line-76"></span><span class="hs-comment">-- a canonical element. Keeps the descriptor of point2.</span><span>
</span><span id="line-77"></span><span id="local-6989586621679651369"><span id="local-6989586621679651370"><span class="annot"><a href="Distribution.Utils.UnionFind.html#union"><span class="hs-identifier hs-type">union</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651370"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651369"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651370"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651369"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.ST.html#ST"><span class="hs-identifier hs-type">ST</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651370"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-special">)</span></span></span><span>
</span><span id="line-78"></span><span id="union"><span class="annot"><span class="annottext">union :: forall s a. Point s a -&gt; Point s a -&gt; ST s ()
</span><a href="Distribution.Utils.UnionFind.html#union"><span class="hs-identifier hs-var hs-var">union</span></a></span></span><span> </span><span id="local-6989586621679651274"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651274"><span class="hs-identifier hs-var">refpoint1</span></a></span></span><span> </span><span id="local-6989586621679651273"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651273"><span class="hs-identifier hs-var">refpoint2</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-79"></span><span>    </span><span id="local-6989586621679651272"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651272"><span class="hs-identifier hs-var">point1</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Point s a)
forall s a. Point s a -&gt; ST s (Point s a)
</span><a href="Distribution.Utils.UnionFind.html#repr"><span class="hs-identifier hs-var">repr</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651274"><span class="hs-identifier hs-var">refpoint1</span></a></span><span>
</span><span id="line-80"></span><span>    </span><span id="local-6989586621679651271"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651271"><span class="hs-identifier hs-var">point2</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Point s a)
forall s a. Point s a -&gt; ST s (Point s a)
</span><a href="Distribution.Utils.UnionFind.html#repr"><span class="hs-identifier hs-var">repr</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651273"><span class="hs-identifier hs-var">refpoint2</span></a></span><span>
</span><span id="line-81"></span><span>    </span><span class="annot"><span class="annottext">Bool -&gt; ST s () -&gt; ST s ()
forall (f :: * -&gt; *). Applicative f =&gt; Bool -&gt; f () -&gt; f ()
</span><a href="../../base/src/GHC.Base.html#when"><span class="hs-identifier hs-var">when</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651272"><span class="hs-identifier hs-var">point1</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; Point s a -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">/=</span></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651271"><span class="hs-identifier hs-var">point2</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">(ST s () -&gt; ST s ()) -&gt; ST s () -&gt; ST s ()
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-82"></span><span>    </span><span id="local-6989586621679651270"><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651270"><span class="hs-identifier hs-var">l1</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Link s a)
forall s a. Point s a -&gt; ST s (Link s a)
</span><a href="Distribution.Utils.UnionFind.html#readPoint"><span class="hs-identifier hs-var">readPoint</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651272"><span class="hs-identifier hs-var">point1</span></a></span><span>
</span><span id="line-83"></span><span>    </span><span id="local-6989586621679651269"><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651269"><span class="hs-identifier hs-var">l2</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Link s a)
forall s a. Point s a -&gt; ST s (Link s a)
</span><a href="Distribution.Utils.UnionFind.html#readPoint"><span class="hs-identifier hs-var">readPoint</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651271"><span class="hs-identifier hs-var">point2</span></a></span><span>
</span><span id="line-84"></span><span>    </span><span class="hs-keyword">case</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651270"><span class="hs-identifier hs-var">l1</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Link s a
</span><a href="#local-6989586621679651269"><span class="hs-identifier hs-var">l2</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-85"></span><span>        </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Info"><span class="hs-identifier hs-type">Info</span></a></span><span> </span><span id="local-6989586621679651268"><span class="annot"><span class="annottext">STRef s Int
</span><a href="#local-6989586621679651268"><span class="hs-identifier hs-var">wref1</span></a></span></span><span> </span><span id="local-6989586621679651267"><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651267"><span class="hs-identifier hs-var">dref1</span></a></span></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Info"><span class="hs-identifier hs-type">Info</span></a></span><span> </span><span id="local-6989586621679651266"><span class="annot"><span class="annottext">STRef s Int
</span><a href="#local-6989586621679651266"><span class="hs-identifier hs-var">wref2</span></a></span></span><span> </span><span id="local-6989586621679651265"><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651265"><span class="hs-identifier hs-var">dref2</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-86"></span><span>            </span><span id="local-6989586621679651264"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679651264"><span class="hs-identifier hs-var">weight1</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">STRef s Int -&gt; ST s Int
forall s a. STRef s a -&gt; ST s a
</span><a href="../../base/src/GHC.STRef.html#readSTRef"><span class="hs-identifier hs-var">readSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s Int
</span><a href="#local-6989586621679651268"><span class="hs-identifier hs-var">wref1</span></a></span><span>
</span><span id="line-87"></span><span>            </span><span id="local-6989586621679651263"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679651263"><span class="hs-identifier hs-var">weight2</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">STRef s Int -&gt; ST s Int
forall s a. STRef s a -&gt; ST s a
</span><a href="../../base/src/GHC.STRef.html#readSTRef"><span class="hs-identifier hs-var">readSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s Int
</span><a href="#local-6989586621679651266"><span class="hs-identifier hs-var">wref2</span></a></span><span>
</span><span id="line-88"></span><span>            </span><span class="hs-comment">-- Should be able to optimize the == case separately</span><span>
</span><span id="line-89"></span><span>            </span><span class="hs-keyword">if</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679651264"><span class="hs-identifier hs-var">weight1</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&gt;=</span></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679651263"><span class="hs-identifier hs-var">weight2</span></a></span><span>
</span><span id="line-90"></span><span>                </span><span class="hs-keyword">then</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-91"></span><span>                    </span><span class="annot"><span class="annottext">Point s a -&gt; Link s a -&gt; ST s ()
forall s a. Point s a -&gt; Link s a -&gt; ST s ()
</span><a href="Distribution.Utils.UnionFind.html#writePoint"><span class="hs-identifier hs-var">writePoint</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651271"><span class="hs-identifier hs-var">point2</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Point s a -&gt; Link s a
forall s a. Point s a -&gt; Link s a
</span><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-var">Link</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651272"><span class="hs-identifier hs-var">point1</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-92"></span><span>                    </span><span class="hs-comment">-- The weight calculation here seems a bit dodgy</span><span>
</span><span id="line-93"></span><span>                    </span><span class="annot"><span class="annottext">STRef s Int -&gt; Int -&gt; ST s ()
forall s a. STRef s a -&gt; a -&gt; ST s ()
</span><a href="../../base/src/GHC.STRef.html#writeSTRef"><span class="hs-identifier hs-var">writeSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s Int
</span><a href="#local-6989586621679651268"><span class="hs-identifier hs-var">wref1</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679651264"><span class="hs-identifier hs-var">weight1</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Int
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#%2B"><span class="hs-operator hs-var">+</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679651263"><span class="hs-identifier hs-var">weight2</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-94"></span><span>                    </span><span class="annot"><span class="annottext">STRef s a -&gt; a -&gt; ST s ()
forall s a. STRef s a -&gt; a -&gt; ST s ()
</span><a href="../../base/src/GHC.STRef.html#writeSTRef"><span class="hs-identifier hs-var">writeSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651267"><span class="hs-identifier hs-var">dref1</span></a></span><span> </span><span class="annot"><span class="annottext">(a -&gt; ST s ()) -&gt; ST s a -&gt; ST s ()
forall (m :: * -&gt; *) a b. Monad m =&gt; (a -&gt; m b) -&gt; m a -&gt; m b
</span><a href="../../base/src/GHC.Base.html#%3D%3C%3C"><span class="hs-operator hs-var">=&lt;&lt;</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s a -&gt; ST s a
forall s a. STRef s a -&gt; ST s a
</span><a href="../../base/src/GHC.STRef.html#readSTRef"><span class="hs-identifier hs-var">readSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s a
</span><a href="#local-6989586621679651265"><span class="hs-identifier hs-var">dref2</span></a></span><span>
</span><span id="line-95"></span><span>                </span><span class="hs-keyword">else</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-96"></span><span>                    </span><span class="annot"><span class="annottext">Point s a -&gt; Link s a -&gt; ST s ()
forall s a. Point s a -&gt; Link s a -&gt; ST s ()
</span><a href="Distribution.Utils.UnionFind.html#writePoint"><span class="hs-identifier hs-var">writePoint</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651272"><span class="hs-identifier hs-var">point1</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Point s a -&gt; Link s a
forall s a. Point s a -&gt; Link s a
</span><a href="Distribution.Utils.UnionFind.html#Link"><span class="hs-identifier hs-var">Link</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651271"><span class="hs-identifier hs-var">point2</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-97"></span><span>                    </span><span class="annot"><span class="annottext">STRef s Int -&gt; Int -&gt; ST s ()
forall s a. STRef s a -&gt; a -&gt; ST s ()
</span><a href="../../base/src/GHC.STRef.html#writeSTRef"><span class="hs-identifier hs-var">writeSTRef</span></a></span><span> </span><span class="annot"><span class="annottext">STRef s Int
</span><a href="#local-6989586621679651266"><span class="hs-identifier hs-var">wref2</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679651264"><span class="hs-identifier hs-var">weight1</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Int
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#%2B"><span class="hs-operator hs-var">+</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679651263"><span class="hs-identifier hs-var">weight2</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-98"></span><span>        </span><span class="annot"><span class="annottext">(Link s a, Link s a)
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; ST s ()
forall a. HasCallStack =&gt; [Char] -&gt; a
</span><a href="../../base/src/GHC.Err.html#error"><span class="hs-identifier hs-var">error</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;UnionFind.union: repr invariant broken&quot;</span></span><span>
</span><span id="line-99"></span><span>
</span><span id="line-100"></span><span class="hs-comment">-- | Test if two points are in the same equivalence class.</span><span>
</span><span id="line-101"></span><span id="local-6989586621679651360"><span id="local-6989586621679651361"><span class="annot"><a href="Distribution.Utils.UnionFind.html#equivalent"><span class="hs-identifier hs-type">equivalent</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651361"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651360"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Utils.UnionFind.html#Point"><span class="hs-identifier hs-type">Point</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651361"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651360"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.ST.html#ST"><span class="hs-identifier hs-type">ST</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651361"><span class="hs-identifier hs-type">s</span></a></span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span></span></span><span>
</span><span id="line-102"></span><span id="equivalent"><span class="annot"><span class="annottext">equivalent :: forall s a. Point s a -&gt; Point s a -&gt; ST s Bool
</span><a href="Distribution.Utils.UnionFind.html#equivalent"><span class="hs-identifier hs-var hs-var">equivalent</span></a></span></span><span> </span><span id="local-6989586621679651258"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651258"><span class="hs-identifier hs-var">point1</span></a></span></span><span> </span><span id="local-6989586621679651257"><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651257"><span class="hs-identifier hs-var">point2</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Point s a -&gt; Point s a -&gt; Bool)
-&gt; ST s (Point s a) -&gt; ST s (Point s a) -&gt; ST s Bool
forall (m :: * -&gt; *) a1 a2 r.
Monad m =&gt;
(a1 -&gt; a2 -&gt; r) -&gt; m a1 -&gt; m a2 -&gt; m r
</span><a href="../../base/src/GHC.Base.html#liftM2"><span class="hs-identifier hs-var">liftM2</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a -&gt; Point s a -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">(==)</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Point s a)
forall s a. Point s a -&gt; ST s (Point s a)
</span><a href="Distribution.Utils.UnionFind.html#repr"><span class="hs-identifier hs-var">repr</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651258"><span class="hs-identifier hs-var">point1</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Point s a -&gt; ST s (Point s a)
forall s a. Point s a -&gt; ST s (Point s a)
</span><a href="Distribution.Utils.UnionFind.html#repr"><span class="hs-identifier hs-var">repr</span></a></span><span> </span><span class="annot"><span class="annottext">Point s a
</span><a href="#local-6989586621679651257"><span class="hs-identifier hs-var">point2</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-103"></span></pre></body></html>